package com.ma.graph;

import com.ma.graph.mst.UF;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 给你一个points数组，表示 2D 平面上的一些点，其中points[i] = [xi, yi]。
 * <p>
 * 连接点[xi, yi] 和点[xj, yj]的费用为它们之间的 曼哈顿距离：|xi - xj| + |yi - yj|，其中|val|表示val的绝对值。
 * <p>
 * 请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有一条简单路径时，才认为所有点都已连接。
 */
public class Solution1584 {
    public static int minCostConnectPoints(int[][] points) {
        //节点数
        int n = points.length;

        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int xi = points[i][0], yi = points[i][1];
                int xj = points[j][0], yj = points[j][1];
                edges.add(new int[]{i, j, Math.abs(xi - xj) + Math.abs(yi - yj)});
            }
        }
        Collections. sort(edges, (a, b) -> a[2] - b[2]);
        int mst = 0;
        UF uf = new UF(n);
        for (int[] edge : edges) {
            if(uf.connected(edge[0],edge[1])){
                continue;
            }
            uf.union(edge[0],edge[1]);
            mst +=edge[2];
        }
        return mst;
    }

    public static void main(String[] args) {
        //输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
        //输出：20
        int[][] points = {{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}};
        System.out.println(minCostConnectPoints(points));
    }

}
